// CreatMap.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <cmath>
#include <time.h>
using namespace std;

#define STEPX				100
#define STEPY				100
#define NODE_NUMBER			300

typedef struct _neighbor {
	int nodeID;
	_neighbor* next;
}neighbor;

int main()
{
	int i;
	int j;
	int MapType;
	int UserType;
	int NEIGHBOR_RANGE;
	int specific_user;
	int city = 0;
	int user;
	int X1 = 20;
	int X2 = 40;
	int X3 = 60;
	int X4 = 80;
	int Y1 = 20;
	int Y2 = 40;
	int Y3 = 60;
	int Y4 = 80;
	int Startpoint;
	int Starneighbor;
	int neighbor_id;
	int flag = 1;
	int region;
	int basex;
	int basey;
	double neighbor_number;
	double average = 1.44;
	char filename[30];
	ofstream map;
	neighbor** head;
	neighbor* index;
	neighbor* search;
	neighbor* target;

	cout << "Choose a map type:" << endl;
	cout << "1. Sparse" << endl;
	cout << "2. Urban" << endl;
	cout << "3. Two cities" << endl;
	cout << "4. Three cities" << endl;
	cin  >> MapType;

	switch(MapType)
	{
		// sparse map
	case 1:
		break;
		// urban map
	case 2:
		X1 = 10;
		X2 = 20;
		X3 = 80;
		X4 = 90;
		Y1 = 10;
		Y2 = 20;
		Y3 = 80;
		Y4 = 90;
		break;
		// two cities
	case 3:
		X1 = 6;
		X2 = 46;
		X3 = 52;
		X4 = 92;
		Y1 = 10;
		Y2 = 20;
		Y3 = 80;
		Y4 = 90;
		break;
		// three cities
	case 4:
		X1 = 30;
		X2 = 35;
		X3 = 65;
		X4 = 70;
		Y1 = 10;
		Y2 = 20;
		Y3 = 80;
		Y4 = 90;
		break;
	default:
		cout << "Error: A wrong number. " << endl;
		break;
	}

	// specialise mode on sparse or urban map
	if(MapType == 1 || MapType == 2)
		{
			cout << "Population"       << endl
				 << "1. Random"         << endl
				 << "2. Business city" << endl
				 << "3. college city"  << endl;
			cin >> specific_user;
		}

	srand((unsigned int)time(NULL));
	head = new neighbor*[NODE_NUMBER];
	for(i = 0;i<NODE_NUMBER;i++)
		head[i]  = NULL;

	cout << "Enter map's name (Less than 30 char)";
	cin >> filename;
	map.open(strcat(filename,".txt"));

	cout << "Enter average number of neighbors" << endl;
	cin >> NEIGHBOR_RANGE;

	for(i=1;i<=NODE_NUMBER;i++)
	{
		// Decide how much friend this node has 
		neighbor_number = rand() % 1024 + 1;
		neighbor_number = 10 - ((log10(neighbor_number) / log10((double)2)));
		neighbor_number = ceil(neighbor_number/average*NEIGHBOR_RANGE);

		// if there are no friend in head[i-1], then store first friend
		if(head[i-1] == NULL)
		{
			neighbor_id = rand() % NODE_NUMBER + 1;
			head[i-1] = new neighbor;
			index = head[i-1];
			index->next = NULL;
			index->nodeID = neighbor_id;
			if(head[neighbor_id-1] == NULL)
			{
				head[neighbor_id-1] = new neighbor;
				head[neighbor_id-1]->nodeID = i;
				head[neighbor_id-1]->next = NULL;
			}
			else
			{
				target = head[neighbor_id-1];
				while(target->next != NULL)
				{
					target = target->next;
				}
				target->next = new neighbor;
				target = target->next;
				target->nodeID = i;
				target->next = NULL;
			}
		}

		// Store rest friends
		index = head[i-1];
		for(j=0;j<neighbor_number;j++)
		{
			// search duplicated friend
			flag = 0;
			while(flag == 0)
			{
				neighbor_id = rand() % NODE_NUMBER + 1;
				search = head[i-1];
				while(search != NULL)
				{
					if(search->nodeID == neighbor_id)
						break;
					else
						search = search->next;
				}
				if(search == NULL && neighbor_id != i)
					flag = 1;
			}
			// insert friend
			index->next = new neighbor;
			index = index->next;
			index->nodeID = neighbor_id;
			index->next = NULL;
			if(head[neighbor_id-1] == NULL)
			{
				head[neighbor_id-1] = new neighbor;
				head[neighbor_id-1]->nodeID = i;
				head[neighbor_id-1]->next = NULL;
			}
			else
			{
				target = head[neighbor_id-1];
				while(target->next != NULL)
				{
					target = target->next;
				}
				target->next = new neighbor;
				target = target->next;
				target->nodeID = i;
				target->next = NULL;
			}
			
		}

		map << i << " ";
		region = rand() % 100;
		//randomly generate the location of node
		if(region < X1)
			basex = 0*STEPX;
		if(region >= X1 && region < X2)
			basex = 1*STEPX;
		if(region >= X2 && region < X3)
			basex = 2*STEPX;
		if(region >= X3 && region < X4)
			basex = 3*STEPX;
		if(region >= X4 && region < 100)
			basex = 4*STEPX;
		region = rand() % 100;
		if(region < Y1)
			basey = 0*STEPY;
		if(region >= Y1 && region < Y2)
			basey = 1*STEPY;
		if(region >= Y2 && region < Y3)
			basey = 2*STEPY;
		if(region >= Y3 && region < Y4)
			basey = 3*STEPY;
		if(region >= Y4 && region < 100)
			basey = 4*STEPY;

		map << basex+rand()%100 << " " << basey+rand()%100 << " ";

		//generate the location of node
		switch(specific_user)
		{
		case 1:
			UserType = rand() % 5;
			break;
		case 2:
			if(basex == 2*STEPX && basey ==  2*STEPY)
			{
				city++;
				user = rand() % 100;
				if(user < 10)
					UserType = 0;
				else if(user >= 10 && user < 20)
					UserType = 1;
				else if(user >= 20 && user < 25)
					UserType = 2;
				else if(user >= 25 && user < 30)
					UserType = 3;
				else if(user >= 30 && user < 100)
					UserType = 4;
			}
			else
			{
				user = rand() % 100;
				if(user < 10)
					UserType = 0;
				else if(user >= 10 && user < 15)
					UserType = 1;
				else if(user >= 15 && user < 65)
					UserType = 2;
				else if(user >= 65 && user < 95)
					UserType = 3;
				else if(user >= 95 && user < 100)
					UserType = 4;
			}
			break;
		case 3:
			if(basex == 2*STEPX && basey ==  2*STEPY)
			{
				city++;
				user = rand() % 100;
				if(user < 10)
					UserType = 0;
				else if(user >= 10 && user < 80)
					UserType = 1;
				else if(user >= 80 && user < 85)
					UserType = 2;
				else if(user >= 95 && user < 90)
					UserType = 3;
				else if(user >= 90 && user < 100)
					UserType = 4;
			}
			else
			{
				user = rand() % 100;
				if(user < 10)
					UserType = 0;
				else if(user >= 10 && user < 15)
					UserType = 1;

				else if(user >= 15 && user < 65)
					UserType = 2;
				else if(user >= 65 && user < 95)
					UserType = 3;
				else if(user >= 95 && user < 100)
					UserType = 4;
			}
			break;
		}
		map << UserType << " ";


		index = head[i-1];
		while(index != NULL)
		{
			map << index->nodeID << " ";
			region = rand() % 100;
			
			index = index->next;
		}
		map << endl;
	}
	map.close();

	return 0;
}